typedef struct {
    int top;
    int *nums;
} stack_t;

void stack_init(stack_t **s, int size)
{
    *s = malloc(sizeof(stack_t));
    (*s)->top = -1;
    (*s)->nums = calloc(size, sizeof(int));
}

int is_empty(stack_t *s)
{
    return (s->top <= -1);
}

void push(stack_t *s, int value)
{
    s->nums[++s->top] = value;
}
int pop(stack_t *s)
{
    return s->nums[s->top--];
}
int top(stack_t *s) 
{
    return s->nums[s->top];
}
#define MAX(a,b) ((a)>(b)? (a):b)
int largestRectangleArea(int* heights, int heightsSize){
    int res = 0;
    stack_t *stack;

    //构造新的高度数组, 两端添0
    int *new_heights = malloc(sizeof(int)*(heightsSize+2));
    int i, len = heightsSize+2;
    new_heights[0] = 0; new_heights[len - 1] = 0;
    for (i = 0; i < heightsSize; i++) {
        new_heights[i+1] = heights[i];
    }

    stack_init(&stack, len);

    // （栈底 → 栈顶）单调递增栈
    for (i = 0; i < len; i++) {
        while (!is_empty(stack) && new_heights[i] < new_heights[top(stack)]) {  //i的高小于栈顶元素的高
            // 0 2 1 5 6 2 3 0
            // 2入栈后，new_heights[i]=1，小于栈顶，2出栈，以2为高的宽为(2-1)
            // 之后1 5 6入栈；到2时，6出栈，面积为6*1；2还是小于5，5出栈，面积为5*2；
            int cur_height = new_heights[pop(stack)];

            // 元素弹出后，新的栈顶就是其左边界
            int width = i - (top(stack) + 1);     
            res = MAX(res, cur_height*width);
        }
        push(stack, i); //大于则入栈
    }  
    return res;
}